/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author claudialilianaleivadesiguenza
 */

import java.util.Iterator;
public class Dijkstra {
    
    public Dijkstra(){
    }
    
    
    public Map<String,ComparableAssociation<Integer,Edge<String,Integer>>> algoritmoDijkstra(Graph<String,Integer> g, String start)
	// pre: g is a graph; start is source vertex
	// post: returns a dictionary of vertex-based results
	// value is association (total-distance,prior-edge)
	{
	// keep a priority queue of distances from source
		PriorityQueue<ComparableAssociation<Integer,Edge<String,Integer>>>	q =  new SkewHeap<ComparableAssociation<Integer,Edge<String,Integer>>>();
		// results, sorted by vertex
		Map<String,ComparableAssociation<Integer,Edge<String,Integer>>> result = new Table<String,ComparableAssociation<Integer,Edge<String,Integer>>>();
		String v = start; // last vertex added
		// result is a (total-distance,previous-edge) pair
		ComparableAssociation<Integer,Edge<String,Integer>> possible = 	new ComparableAssociation<Integer,Edge<String,Integer>>(0,null);
		// as long as we add a new vertex...
		while (v != null)
		{
			if (!result.containsKey(v))
			{
				// visit node v - record incoming edge
				result.put(v,possible);
				// vDist is shortest distance to v
				int vDist = possible.getKey();
				// compute and consider distance to each neighbor
				Iterator<String> ai = g.neighbors(v);
				while (ai.hasNext())
				{
					// get edge to neighbor
					Edge<String,Integer> e = g.getEdge(v,ai.next());
					// construct (distance,edge) pair for possible result
					possible = new ComparableAssociation<Integer,Edge<String,Integer>>(vDist+e.label(), e);
					q.add(possible); // add to priority queue
				}
			}
			// now, get closest (possibly unvisited) vertex
			if (!q.isEmpty())
			{
				possible = q.remove();
				// get destination vertex (take care w/undirected graphs)
				v = possible.getValue().there();
				if (result.containsKey(v))
				v = possible.getValue().here();
			} else {
				// no new vertex (algorithm stops)
				v = null;
			}
		}
		return result;
	}
}
